let isSingle = val => val % 2 === 1;
let nums = [1,3,-1,-3,5,3,6,7];
let k = 4;
class PQ {
    constructor(compareFn = (a, b) => a > b) {
      this.data = [];
      this.size = 0;
      this.compareFn = compareFn;
    }
    offer(val) { // 新增
      this.data.push(val);
      this.shiftUp(this.size++);
    }
    poll() { // 移除并返回堆顶
      if (!this.size) return null;
      this.swap(0, --this.size);
      let res = this.data.pop();
      this.shiftDown(0);
      return res;
    }
  
    peek() { // 获取堆顶元素
      return this.data[0] ?? null;
    }
  
    getParentIndex(index) {
      return index - 1 >> 1
    }
  
    getChildIndex(index) {
      return (index << 1) + 1
    }
  
    shiftDown(index) {
      let childIndex = this.getChildIndex(index);
      while (childIndex < this.size) {
        if (childIndex + 1 < this.size && this.compareFn(this.data[childIndex + 1], this.data[childIndex])) {
          childIndex++;
        }
        if (this.compareFn(this.data[index], this.data[childIndex])) break;
        this.swap(index, childIndex);
        index = childIndex;
        childIndex = this.getChildIndex(index);
      }
    }
  
    shiftUp(index) {
      let parentIndex = this.getParentIndex(index);
      while (parentIndex >= 0 && this.compareFn(this.data[index], this.data[parentIndex])) {
        this.swap(index, parentIndex);
        index = parentIndex;
        parentIndex = this.getParentIndex(index);
      }
    }
  
    swap(a, b) {
      [this.data[a], this.data[b]] = [this.data[b], this.data[a]];
    }
  }
  
var medianSlidingWindow = function (nums, k) {
  let minPQ = new PQ((a, b) => a < b);
  let maxPQ = new PQ();
  let res = [];
  let map = new Map(), middle = null;
  for (let i = 0; i < k; i++) {
    maxPQ.offer(nums[i]);
  }
  for (let i = 0; i < Math.floor(k / 2); i++) {
    minPQ.offer(maxPQ.poll());
  }
  middle = isSingle(k) ? maxPQ.peek() : (maxPQ.peek() + minPQ.peek()) / 2;
  res.push(middle);
  let balance = 0;

  for (let i = k; i < nums.length; i++) {
    let last = nums[i - k], num = nums[i];
    if (last <= middle) balance--;
    else balance++;
    map.set(last, (map.get(last) ?? 0) + 1);
    if (num > minPQ.peek()) {
      minPQ.offer(num);
      balance--;
    } else {
      maxPQ.offer(num);
      balance++;
    }
    if (balance > 0) minPQ.offer(maxPQ.poll());
    else if (balance < 0) maxPQ.offer(minPQ.poll());
    balance = 0;

    while (maxPQ.size && map.get(maxPQ.peek())) map.set(maxPQ.peek(), map.get(maxPQ.poll()) - 1);
    while (minPQ.size && map.get(minPQ.peek())) map.set(minPQ.peek(), map.get(minPQ.poll()) - 1);

    if (isSingle(k)) {
      middle = maxPQ.peek();
    } else {
      middle = (minPQ.peek() + maxPQ.peek()) / 2;
    }

    res.push(middle)
  }
  return res;
};
console.log(medianSlidingWindow(nums,k));
